package secondary

/*
	统计一个数字在排序数组中出现的次数。

	示例 1:

	输入: nums = [5,7,7,8,8,10], target = 8
	输出: 2
	示例2:

	输入: nums = [5,7,7,8,8,10], target = 6
	输出: 0

	提示：

	0 <= nums.length <= 105
	-109<= nums[i]<= 109
	nums是一个非递减数组
	-109<= target<= 109

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
// 找到左右边界、然后计算
func search(nums []int, target int) int {
	// 给定l,r、使得nums(l,r)左开右开区间中包含的都是target、最终长度应该是r-l-1
	l, r := 0, 0
	i := 0
	j := len(nums) - 1
	// 找到左边界
	for i <= j {
		mid := (i + j) / 2
		if nums[mid] < target {
			i = mid + 1
		} else {
			j = mid - 1
		}
	}
	l = j
	i = 0
	j = len(nums) - 1
	for i <= j {
		mid := (i + j) / 2
		if nums[mid] > target {
			j = mid - 1
		} else {
			i = mid + 1
		}
	}
	r = i
	return r - l - 1
}
